#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "stack"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

 

示例 1：


输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//todo 抄的 中序遍历标准写法
vector<int> inorderTraversal(TreeNode *root) {
    vector<int> res;
    stack<TreeNode *> st;
    auto p = root;
    while (p || !st.empty()) {
        while (p) {
            st.push(p);
            p = p->left;
        }
        auto node = st.top();
        st.pop();
        res.emplace_back(node->val);
        p = node->right;
    }
    return res;
}

//倒中序
//void traversal(TreeNode* root) {
//    stack<TreeNode*> st;
//    TreeNode* cur = root;
//    while (cur != NULL || !st.empty()) {
//        if (cur != NULL) {
//            st.push(cur);
//            cur = cur->right; // 右
//        } else {
//            cur = st.top(); // 中
//            st.pop();
//            cur->val += pre;
//            pre = cur->val;
//            cur = cur->left; // 左
//        }
//    }
//}

vector<int> inorderTraversal(TreeNode *root) {
    vector<int> res;
    stack<TreeNode *> st;
    auto p = root;
    while (p || !st.empty()) {
        if (p) {
            st.push(p);
            p = p->left;
        } else {
            p = st.top();
            res.emplace_back(p->val);
            st.pop();
            p = p->right;
        }

    }
    return res;
}


//vector<int> inorderTraversal(TreeNode* root) {
//    vector<int> ret;
//    stack<TreeNode*> s;
//    if (!root)
//        return ret;
//    s.push(root);
//    TreeNode* temp=root;
//    while (!s.empty()|| temp)
//    {
//        //一直到最左边
//        while (temp)
//        {
//            s.push(temp);
//            temp=temp->left;
//        }
//        //
//
//        temp=s.top();
//        ret.push_back(temp->val);
//        s.pop();
//
//        if (temp->right)
//            s.push(temp->right);
//
//
//    }
//
//
//
//    return ret;
//
//}